package hzk.codex2016.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class Traversals {

	// https://leetcode.com/problems/binary-tree-paths/
	public List<String> binaryTreePaths(TreeNode root) {
		class S {
			int[] path = new int[60];
			List<String> ans = new ArrayList<>();

			void dfs(int h, TreeNode no) {
				if (no == null)
					return;
				if (no.left == null && no.right == null) {
					path[h] = no.val;
					addAns(h);
					
				}
				dfs(h + 1, no.left);
				dfs(h + 1, no.right);
			}

			void addAns(int h) {
				StringBuffer sb = new StringBuffer();
				for (int i = 0; i < h; i++) {
					sb.append(path[i]).append("->");
				}
				sb.append(path[h]);
				ans.add(sb.toString());
			}
		}
		S s=new S();
		s.dfs(0, root);
		return s.ans;
	}

	/**
	 * https://leetcode.com/problems/binary-tree-inorder-traversal/#
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal2(TreeNode root) {
		class S {
			List<Integer> trip = new ArrayList<>();

			void dfs(TreeNode no) {
				if (no == null)
					return;
				dfs(no.left);
				trip.add(no.val);
				dfs(no.right);
			}
		}
		S s = new S();
		s.dfs(root);
		return s.trip;
	}

	// non-recursion implement
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> trip = new ArrayList<>();
		Stack<TreeNode> st = new Stack<>();

		TreeNode p = root;
		for (p = root; p != null; p = p.left)
			st.push(p);

		while (!st.empty()) {
			trip.add((p = st.pop()).val);
			for (p = p.right; p != null; p = p.left)
				st.push(p);
		}
		return trip;
	}

	/**
	 * https://leetcode.com/problems/binary-tree-level-order-traversal/
	 * 
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrder(TreeNode root) {
		if (root == null)
			return Collections.emptyList();
		Queue<TreeNode> q = new LinkedList<>();

		q.offer(root);
		TreeNode dad;
		List ret = new ArrayList();
		while (!q.isEmpty()) {
			List<Integer> row = new ArrayList<>();
			for (int cnt = q.size(); cnt > 0; cnt--) {
				dad = q.poll();
				row.add(dad.val);

				if (dad.left != null) {
					q.offer(dad.left);
				}
				if (dad.right != null) {
					q.offer(dad.right);
				}

			}
			ret.add(row);
		}
		return ret;
	}

	// https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		class S {
			int[] preorder, inorder;
			Map<Integer, Integer> inorderIdMap; // val->idx

			TreeNode build(int pre1, int pre2, int in1, int in2) {
				// System.out.printf("==%d %d %d %d\n",pre1,pre2,in1,in2);
				if (pre1 > pre2)
					return null;
				int v = preorder[pre1];
				TreeNode me = new TreeNode(v);
				if (pre1 == pre2)
					return me;
				// int x;for (x=in1;x<=in2 && v!=inorder[x];x++);
				int x = inorderIdMap.get(v);
				me.left = build(pre1 + 1, pre1 + x - in1, in1, x - 1);
				me.right = build(pre1 + x - in1 + 1, pre2, x + 1, in2);
				return me;
			}
		}

		S s = new S();
		s.preorder = preorder;
		s.inorder = inorder;
		int n = preorder.length;
		s.inorderIdMap = new HashMap<>();
		for (int i = 0; i < n; i++) {
			s.inorderIdMap.put(s.inorder[i], i);
		}
		return s.build(0, n - 1, 0, n - 1);

	}

	public static void main(String[] args) {
		Traversals me = new Traversals();
		TreeNode tree1 = Trees.from(0, 1, 2, 3, 4, 5, 6, 7, -1, 9, 10, -1, 12, 13, 14, 15, 16, -1, -1, 19, 20);
		Trees.print(tree1);
		System.out.println(me.inorderTraversal(tree1));
		System.out.println(me.inorderTraversal2(tree1));
		System.out.println(me.levelOrder(tree1));

		TreeNode tree2 = me.buildTree(new int[] { 1, 2, 4, 5, 8, 3, 6, 9, 7 }, new int[] { 4, 2, 8, 5, 1, 6, 9, 3, 7 });
		Trees.print(tree2);
		System.out.println(me.binaryTreePaths(tree2));
	}

}
